基于边界网关协议(border gateway protocol,简称BGP)[1]的域间路由系统是互联网的核心基础设施,路由劫持是BGP路由系统当前所面临的最严重的安全威胁之一.当路由劫持发生时,以被劫持网络为目的地的网络流量有可能会被路由到发起路由劫持的攻击者,因此,路由劫持可被用作攻击手段实现多种目的,例如:丢弃所吸附的网络流量,制造路由黑洞,阻断被劫持网络提供的服务;使用属于被劫持网络的IP地址发送垃圾邮件,隐藏垃圾邮件的真实来源[2];模拟被劫持网络提供的服务,实现网络钓鱼;将吸附的流量发回到被劫持网络,实现隐蔽的“中间人攻击”[3].在互联网发展的历程中,路由劫持事件时有发生,并严重干扰了互联网的正常运行,影响较大的有1997年的AS7007事件[4]、2008年巴基斯坦电信管理局劫持YouTube[5]等.在这些事件中,被劫持网络提供的服务都被中断两个小时以上,造成了重大的社会影响和经济损失.

业界在防范路由劫持方面做出了大量努力,但迄今仍然缺乏有效的防护手段.造成这种状况的原因包括:

(1) BGP安全模型的脆弱性.BGP假设接收到的路由信息是可信和可靠的,使BGP对于针对路由内容的攻击特别是路由劫持非常脆弱[6].鉴于当前域间路由系统的巨大规模,更换或升级BGP都非常困难,因此,BGP安全模型上的脆弱性将长期存在;

(2) ISP(Internet service provider,网络运营商)之间缺乏有效的信息共享和协同.每个ISP独立地运行自己的网络,客户信息、路由策略均被视为商业秘密,而对路由劫持的防范需要ISP之间进行有效的协同.以路由劫持中的前缀劫持为例,其体现为前缀和宣告者自治系统(autonomous system,简称AS)对应关系的变化.由于当前并不存在一个权威的机构或数据源能够准确地跟踪、提供这种对应关系,仅前缀的拥有者本身(受害者AS)能够判明这种变化是否合理.但如本文第2节所述,这种变化传播到受害者AS的概率很低.

本文的贡献包括:

(1) 对AS基于BGP路由信息自我发现路由劫持的概率(免疫能力)进行建模,给出了AS自我免疫的充分条件、必要条件和该免疫能力的上界.实验结果表明,超过80%以上的AS对路由劫持完全没有免疫能力,仅有不超过0.26%的AS的免疫力高于85%;

(2) 揭示了导致AS对路由劫持免疫能力低下的提供商栅栏现象——提供商优选从客户AS学到的路由,在路由劫持发生时阻碍了劫持路由向受害者AS的传播;

(3) 为了克服提供商栅栏,提高AS对路由劫持的免疫能力,设计了协同监测机制.参与协同的每个AS从协同邻居学习相关于本AS所属网络的路由用于监测,不干扰路由系统的正常功能;向每个协同邻居只输出相关于该邻居的路由,所暴露的路由信息分布在不同邻居之间,保护了参与者AS的隐私;由参与者AS检测针对于所属网络的路由劫持,回避了第三方难以区分正常路由变化和路由劫持的难题;

(4) 提出了一种启发式协同邻居选取策略,以较低的算法复杂度实现了较高的安全能力.实验结果表明,仅与25个自治系统进行协同,就可将对路由劫持的免疫能力提高到高于95%的水平.

本文第1节介绍BGP和路由劫持的相关背景.第2节对AS基于BGP路由信息感知路由劫持的能力进行建模,给出AS自我免疫的充分条件和必要条件,对该免疫能力的上界进行评估,并揭示导致AS对路由劫持免疫力低下的提供商栅栏现象.第3节介绍防范路由劫持的协同监测方法和协同邻居选取策略.第4节对协同监测方法的部署效果进行评估.最后,第5节介绍相关工作并展望未来的研究方向.

为了增强可扩展性,互联网采用了层次式的路由体系结构,在自治系统(autonomous system,简称AS)粒度上分为域内和域间两个层次.自治系统定义为运行在统一策略之下,向外展示出一致的路由策略的一组路由设备[1].AS内部使用域内路由协议,如OSPF,IS-IS和RIP;AS之间使用域间路由协议.BGP是当前域间路由协议事实上的标准,其作用是在AS之间交换网络可达性信息.

为了实现全网范围内的连通性,每个AS都必须借助邻居AS转发去往/来自非邻居AS的数据流量.AS之间存在4种商业关系:提供商-客户关系(provider-customer,简称p2c),客户-提供商关系(customer-provider,简称c2p),对等体关系(peer-peer,简称p2p)和同胞关系(sibling-sibling,简称s2s).在p2c和c2p关系中,客户AS向提供商AS付费购买数据转发服务;建立p2p关系的两个AS通常具有相当的规模,彼此免费为对方转发数据流量;建立s2s关系的双方一般同属于一个机构,不涉及费用结算,通常互为访问外部网络的备份连接.这4种关系中, p2c(c2p)关系最为普遍,p2p次之,s2s最为少见.以CAIDA[7]推断的AS间商业关系数据为例(基于2010年1月20日的路由表),各种商业关系的数量及比重分为69191(92.3%),5591(7.4%)和219(0.3%).鉴于s2s关系的比例很小,且和p2p关系相似,在很多研究中都被作为p2p连接处理[8],本文采取了相同的处理方式.在Internet的AS级拓扑中,c2p连接可以看作是一条从客户到提供商的有向边,记为®.类似地,用¬表示一条p2c连接,用«表示p2p连接.本文中主要用到的符号及其定义见表 1.

定义1(客户路由(customer route)、对等体路由(peer route)和提供商路由(provider route)). 一个AS从客户、对等体和提供商学到的路由分别称为客户路由、对等体路由和提供商路由.

Internet的AS级拓扑呈现出明显的层次特性.根据在层次结构中所处位置,AS被分为核心层AS(Tier1或Tier1 AS),传输层AS(transit)和边缘层AS(stub).Tier1 AS之间通过直接的对等连接(p2p)全互联,处在Internet路由层次结构的最顶层,是整个Internet的核心.Tier1 AS没有提供商,传输层AS既有提供商也有客户,而边缘层AS没有客户.如图 2所示,自治系统A,B属于核心层,C,D,E属于传输层,F,G,H是边缘层的自治系统.

AS对其域内的路由设备具有完全的控制,因此,每个AS可以独立地制定路由策略以实现其利益诉求.尽管这些路由策略从单个AS的角度来看是正确的,但多个AS之间的路由策略却可能发生冲突,进而在路由系统中造成持续的震荡[9].Griffin等人研究了AS路由策略对BGP稳定性的影响,指出AS间的路由策略不存在竞争环(dispute wheel)是BGP系统稳定的一个充分(非必要)条件[9],但对竞争环进行检测是NP-Complete的[10].Gao和Rexford基于前述章节中的AS商业关系模型和Internet路由结构的层次特性,通过约束AS的路由输入、选择和输出策略,给出了一个操作性更强的充分条件,称为Gao-Rexford约束[11, 12].该约束较好地反映了ISP逐利的特性,在刻画BGP路由行为方面得到了较为广泛的应用,如文献[13]等.该约束具体包含以下3点内容:

· GR1:严格层次特性.AS级拓扑不存在c2p(p2c)的环路,即,任何AS都不能间接地成为自己的提供商(客户);

· GR2:路由选择策略.AS在进行路由选择时,客户路由优先于对等体路由,进而优先于提供商路由.其原因在于:选择客户AS作为下一跳可以赢利,选择对等体AS可以实现免费转发,而选择提供商AS则需要付费;

· GR3:路由输入/输出策略.从提供商和对等体AS学到的路由只允许向客户AS宣告,从客户AS学到的路由可以向所有邻居AS宣告.

如果一条AS路径经过的所有AS都遵循GR3,那么该路径满足“无谷底”(valley-free)特性[11].即,AS路径穿过一条p2c或p2p连接后,不能再穿过c2p或p2p连接.例如,图 2中的AS路径C®A¬D¬G符合无谷底特性,而C®A¬D®B不符合,因为该路径在穿过A¬D(p2c连接)之后又穿过了D®B(c2p连接).由于在Internet路由层次结构中提供商所处层次一般要高于客户,我们将一个AS经过连续的c2p/p2c连接(1条或多条)到达另一个AS的过程称为“上坡/下坡”,相应的路径序列称为“上坡路径/下坡路径”.“无谷底”特性对客户路由、对等体路由和提供商路由的存在形式做出了限制,如图 1所示.

一条BGP路由包含两组属性:目的地标识(网络前缀,prefix)和去往该目的地的路径属性(path attribute)[1].路径属性包括ORIGIN,MULTI_EXIT_DISC,LOCAL_PREF和AS_PATH等.BGP利用AS_PATH属性来避免AS级的路由环路:每个AS将路由传播给邻居AS之前,需要把自己的AS号添加到该路由的AS_PATH列表的左端.接收方AS通过检查自己的AS号是否出现在路由的AS_PATH列表中来判明本AS是否已处理过该路由.

定义2(源AS、下一跳AS). 考虑到与本文内容的相关性,BGP路由r被简化为二元组r=(d,vk-1…v1v0),其中:d是网络前缀,表示一块连续的IP地址;vk-1…v1v0是r的AS_PATH属性的AS列表.最右侧的v0是网络前缀d的所有者,称为源AS(r.origin);路由r经过的不同于源AS的第1个AS,称为下一跳AS(r.nexthop).例如,若v1¹v0,则v1是r的下一跳AS.

BGP是单路径协议.对于任意AS,去往一个目的网络可能会存在多条路由,但是只有最优路由才被用于数据转发和向BGP邻居通告.BGP的最优路由选择(以下简称路由选择)是一个复杂的过程,更多细节可参见文献[1].在理论分析中,我们仅考虑选择:

(1) 具有最高的LOCAL_PREF值的路由(GR2);

(2) 具有最短AS_PATH长度的路由.

RouteViews[14]和RIPE-RIS[15]是分别由美国俄勒冈州立大学和欧洲网络协调中心(RIPE Network Coordination Centre)设立的BGP路由数据发布服务.它们与数百个AS建立了BGP会话,并周期性地发布从这些AS获得的路由表和路由更新数据.根据这些数据,我们可以获知这数百个AS的路由决策结果,即,这些AS去往各个目的网络的AS级路径及变化.

为了劫持到前缀d的路由,攻击者自治系统X通常伪造并向邻居AS宣告一条到特定前缀d¢的长度为k的AS路径,记为p.不失一般性,令p=vk-1…v0.为了避免攻击行为被邻居AS察觉,vk-1通常是攻击者X本身.注意到,当k>1时,宣告路由的AS(X)并不等于路由的源AS(v0).更一般地,定义路由的发起者如下:

定义3(路由r的发起者AS(initiator AS)). 在路由r传播所经过的AS中,若某AS向邻居传播的路由并非学自于其他邻居,称该AS为r的发起者.

根据d¢和d之间的关系以及k的长度,对路由劫持的分类可以从两个维度上进行:

· 在一个维度上,根据d¢是d的父前缀(d¢Éd)、子前缀(d¢Ìd)还是d本身(d¢=d),路由劫持可分为“父前缀劫持”、“子前缀劫持”和“确切前缀劫持”.由于BGP中路由的传播在前缀粒度上独立进行,“父前缀劫持”或“子前缀劫持”中的劫持路由会传播到受害者AS而被发现,攻击效果易于预测,因此,本文中主要讨论对“确切前缀劫持”的防范.但如本文第3节所示,本监测方法也具备对“父前缀劫持”和“子前缀劫持”的防范能力;

· 在另一个维度上,k=1对应于“非法的源AS”攻击,也就是通常所说的“前缀劫持”;k=2对应于“下一跳劫持”.前缀劫持在BGP中表现为“多源AS(multiple origin ASes,简称MOAS)”冲突[16],易于被鉴别;相比而言,通过伪造长度大于1的AS路径进行路由劫持具有更强的隐蔽性,因为仅有被伪造的邻接关系所涉及的AS才能鉴别该攻击.理论上,攻击者可以伪造长度任意的AS路径进行路由劫持,但攻击效果(如吸附的流量)会随k的增加而迅速衰减.本文中只考虑k=1,2时的路由劫持,这也是已报道的路由劫持事件中最常见的情形.

将Internet在AS级的拓扑表示为无向图G=áV,E,Rñ,其中,V是AS集合,E是AS节点之间的边的集合,R是E到集合{p2c,c2p,p2p}的映射.由于AS级Internet拓扑的演化相对缓慢[17],本文假定在一定时间内G相对不变.G中仅有AS u宣告了一个网络前缀d.本文中用Neigh(u)表示u在G中所有邻居AS的集合,Neigh(u)={v| "vÎVÙ(u,v)ÎE},并用Prov(u),Cust(u)和Peer(u)分别表示u的提供商、客户和对等体邻居AS的集合.以图 1为例,Neigh(C)={A,D,F},Prov(C)={A},Cust(C)={F},Peer(C)={D}.

本文在对AS自我免疫能力建模的过程中,除了引入Gao-Rexford约束,还作如下假设:

假设1(唯一性假设). 每个AS到一个前缀只能选择一条最优路由,一对AS之间只存在一种商业关系.

假设2(攻击策略假设). 为了最大化攻击效果,AS发起路由劫持时,向自己所有的邻居宣告伪造的路由.

假设3(连通性假设). 在路由劫持发生之前,V中任意两个自治系统之间相互可达.

定义4(影响范围V(i)). AS i是前缀d的一个发起者,待BGP收敛后,AS i的影响范围定义为V中选择了i发起的路由作为最优路由的AS集合,记为V(i).当前缀d在整个路由系统中只有一个发起者i时,基于连通性假设(假设3),V=V(i);但是当存在多于一个发起者时,V(i)取决于这多个发起者发起的路由在路由系统中扩散、传播和相互作用.在下文中,如果AS xÎV且xÎV(a)(a为攻击者AS),则称x被污染.

路由劫持发生时,若劫持路由传播到了受害者AS,称受害者AS对此路由劫持免疫(也称为自我免疫).此定义基于两个假设:

(1) 绝大多数AS都在域内部署了用于网络管理、测量和信息采集的设施,只要劫持路由传播到了受害者AS的路由器,无论该劫持路由是否被选为最优路由,我们都认为受害者AS能感知到该路由劫持;

(2) 之后,受害者AS可以采取反制措施以消除路由劫持的影响,如宣告被劫持网络的子前缀等.

假设V\{u}中的每个AS对u发起路由劫持的概率相同,定义u对路由劫持的免疫能力Áu如下:

定义5(免疫能力Áu). AS u的自我免疫能力Áu=|Cu|/(|V|-1),其中,Cu是一个AS集合,u对从该集合中的每个AS发起的路由劫持都免疫.

根据BGP路由决策模型,一个AS是否会被污染,不仅取决于它接收到的攻击者a发起的劫持路由,还取决于它到受害者AS u的路由.下面首先对路由劫持发生前V中AS使用的去往u的路由进行讨论.

定义6. 提供商闭包yu是u仅通过上坡路径就能到达的自治系统的集合.换言之,yu中的AS可以通过下坡路径到达u.以图 1为例,yF={C,D,A,B},yE={B}.

定义7. 客户闭包zu是u仅通过下坡路径就能到达的自治系统的集合,换言之,zu中的AS可以通过上坡路径到达u.以图 1为例,zC={F},zF=Æ.

根据上述定义,对于去往u的最优路由选择,yu中的AS选择的一定是客户路由;相反,zu中的AS选择的一定不是客户路由.证明过程见推论1和推论2.

推论1. 仅yu中的AS有到达u的客户路由,且yu中的AS选择的去往u的路由一定是客户路由.

证明:首先证明充分性.根据定义,"xÎyu,存在从u到x的一条上坡路径u®…®y®x(y是到x前的最后一跳);相应地,存在一条从x到u的下坡路径x¬y¬…¬u.因此,x有通过客户y去往u的客户路由.然后证明唯一性.假设$xÏyu,x从其客户y学到一条到u的路由.根据图 2列举的7种模式,y宣告给x的去往u的路由只能属于模式VII,是一条下坡路径,记为y¬…¬u,故x¬y¬…¬u也是一条下坡路径,故xÎyu,与题设矛盾.

根据充分性证明,yu中的AS一定有到u的客户路由.根据GR2,它们选择的去往u的路由一定是客户路由.

推论2. yuÇzu=Æ,即u的提供商闭包和客户闭包之间不存在交集.结合推论1,u的客户闭包中的AS都没有去往u的客户路由.该推论事实上是GR1的外延.

证明:假设$xÎyu且xÎzu,根据提供商闭包的定义,从u到x存在一条上坡路径u®…®x;根据客户闭包的定义,从u到x存在一条下坡路径u¬…¬x.若这两条路径除u和x外不存在交点,则它们在u和x之间形成一个闭合环路,与GR1矛盾;若存在交点,不失一般性,记其中一个交点为y,则至少形成两条回路,u®...®y®u和x®...y®x,与GR1矛盾.题设得证.

假设4. yuÇzPeer(u)=Æ,其中,zPeer(u)表示u的对等体的客户闭包.假设4指u的提供商闭包和u的对等体的客户闭包不存在交集,进而u的对等体的客户闭包中的AS没有到u的客户路由.

虽然Gao-Rexford约束中强调不允许p2c(c2p)连接构成环路,但未对p2p连接做限定.理论上,p2c连接涉及的两个AS中,服务商的网络规模要大于客户,而p2p连接只存在于两个网络规模相当的AS之间,因此,yu中AS的网络规模要大于u的对等体的规模以及u的对等体的客户的规模.据此,我们假设u的提供商闭包和u的对等体的客户闭包之间不存在交集.结合推论1和本假设可知,zPeer(u)中的AS没有去往u的客户路由,但是在实验评估中我们注意到,该假设对于有些自治系统并不成立.

由于BGP中每个AS u只能从邻居AS学习路由,直观上,AS u对AS a发起的路由劫持免疫当且仅当:$xÎ Neigh(u)ÇV(a),x向u输出了到前缀d的路由.即至少存在一个邻居AS,该邻居选择了攻击者发起的劫持路由作为最优路由,且该邻居的路由策略允许它将劫持路由向源AS通告,称为自我免疫的前提.

为了判明u能对何种形态的攻击路由实现自我免疫,我们以u的邻居为研究对象,首先分析它们是否会被攻击路由污染(C1),然后分析若是被污染,它们是否会向u输出攻击路由(C2).具体分析过程见表 2:首先,通过与现有的去往u的路由(existing route to victim)进行比较,依据BGP路由决策模型列举了使u的邻居满足C1的攻击路由的可能形态(route to attacker);然后,根据这些邻居与u之间的商业关系判断C2是否成立,最终得到了能够使u自我免疫的攻击路由的具体形态.

表 2根据与u的商业关系,我们将u的邻居分为提供商、对等体和客户等3类,然后分别讨论这3类邻居能否使C1和C2成立:

(1) "xÎProv(u),x从u学到长度为1的客户路由.根据BGP路由决策模型,只有劫持路由也是客户路由且长度为1时,x才有可能被污染,此时,x用于去往u和a的路由具有同等优先级.注意,x是可能而非一定被污染,因此,表 2中的条件(Bi)只是u自我免疫的可能性条件;

(2) "xÎPeer(u),x从u学到长度为1的对等体路由,仅当劫持路由是长度为1的对等体路由或任意长度的客户路由时,x才被污染.前者是使x被污染的可能条件,后者是充分条件.由于GR3不允许将对等体路由向另一个对等体转发,因此,只有后者同时使C1和C2满足,得到充分条件(Bii);

(3) "xÎCust(u),x从u学到长度为1的提供商路由.当劫持路由是长度为1的提供商路由时,x有可能被污染.当劫持路由是对等体或客户路由时,x一定被污染.根据GR3,每个AS只能向提供商输出客户路由,因此,仅当劫持路由是客户路由时C2才被满足,得到充分条件(Biii).

当攻击者AS发起下一跳劫持时(宣告长度为2的AS路径),表 2中的条件(Bi)不能使C1得到满足,因此,(Bi)不适用于下一跳劫持;条件(Bii)和(Biii)都与劫持路由的AS路径长度无关(any),因此对于下一跳劫持也成立.

条件(Bi/Bii/Biii)是(提供商/对等体/客户)向u输出攻击路由时攻击路由的形态.在(Bi)中,u的提供商学到了去往a的长度为1的客户路由,此时aÎCust(Prov(u))\{u},即u的提供商除u之外的直接客户;在(Bii)中,u的对等体学到了去往a的客户路由,根据GR3对应的7种模式,客户路由的形式仅包含模式VII,因此从该对等体到a必定存在一条下坡路径,此时a∈zPeer(u),即u的对等体的客户闭包;在(Biii)中,u的客户学到了去往a的客户路由,同(Bii),此时aÎzu.

注意到,aÎzPeer(u)是(Bii)成立的必要而非充分条件,但结合假设4,则演化为充分必要条件.例如,不考虑假设4,虽然从u的一个对等体(不妨记为x)到a之间存在一条下坡路径,但若该下坡路径上有的AS优选u而非a发起的路由,那么x可能不被a发起的路由污染,从而不会向u输出a发起的劫持路由.但假设4中zPeer(u)中的AS都没有去往u的客户路由,因此能保证从x到a的下坡路径上的所有AS都优选去往a的客户路由,故u能从x学到a发起的客户路由.同理,aÎzu也只是(Biii)成立的必要而非充分条件,结合推论2后成为充分必要条件.

定理1. 自治系统u对前缀劫持自我免疫的充分条件是攻击者AS aÎNeigh(u)ÈzPeer(u)È{u}.即当a是u的直接邻居,或是u和u的对等体的客户闭包中的AS时,u对a发起的前缀劫持免疫.

证明:

(1) 当aÎNeigh(u)时,根据假设2,每个攻击者都向其所有的直接邻居宣告伪造的攻击路由,因此u可以检测到a发起的前缀劫持;

(2) 当aÎzPeer(u)È{u}\Neigh(u)时:

· 若aÎzPeer(u)\Neigh(u),根据客户闭包的定义,a和u的一个对等体xÎPeer(u)之间存在一条上坡路径p,沿着p的所有AS都属于zx.根据假设4,zx中的AS都没有去往u的客户路由,因此,沿着p的所有AS都会选择a发起的客户路由.故x可以沿p这条路径学到去往前缀d(发起者为a)的客户路由,并通过u«x这条p2p连接宣告给u;

· 若aÎzu\Neigh(u),a和u之间存在一条上坡路径p,沿着p的所有AS都属于zu.由于zu中的AS都没有去往u的客户路由(推论2),因此,沿着p的所有AS都没有去往u的客户路由,却都可以选择沿p学到的客户路由去往a.根据GR2,在选择去往前缀d的路由时,它们都会选择a发起的路由,最终,u沿着p学到a发起的劫持路由.

定理2. 自治系统u对前缀劫持自我免疫的必要条件是攻击者AS aÎNeigh(u)ÈzPeer(u)È{u}ÈCust(Prov(u))).即u对a发起的前缀劫持免疫时,攻击者a或者是u的直接邻居,或者是u和u的对等体的客户闭包中的AS,或者是u的提供商的直接客户.

证明:假设攻击者aÏ{Neigh(u)ÈzPeer(u)È{u}ÈCust(Prov(u)),且u学到了a发起的劫持路由.由于aÏNeigh(u),故a不是u的直接邻居,则至少存在邻居xÎNeigh(u)有xÎV(a),且x将a(x¹a)发起的攻击路由宣告给了u.下面对x与u的商业关系展开讨论:

(1) 若xÎCust(u),由于无谷底原则只允许客户AS x输出形入a®…®x的路径到提供商u(模式VII),根据客户闭包的定义,aÎzu,与题设矛盾;

(2) 若xÎPeer(u),同情形(1),由于无谷底原则只允许x输出形入a®…®x(模式VII)的路径到u,根据客户闭包的定义,aÎzx,考虑到zxÍzPeer(u),因此aÎzPeer(u),与题设矛盾;

(3) 若xÎProv(u),x从u学到的长度为1的客户路由,根据BGP路由决策原理,x必定有去往a的长度为1的客户路由,否则,x不会被劫持路由污染.此时,a必为x的客户,即aÎCust(Prov(u)),与题设矛盾.

综上,题设得证.

类似于对前缀劫持自我免疫的充分、必要条件的推导,可以得到如下结论:

定理3. 自治系统u对下一跳劫持自我免疫的充分必要条件是攻击者AS aÎNeigh(u)ÈzPeer(u)È{u}.

证明:分为充分性证明和必要性证明.充分性证明与定理1完全相同,略去.

必要性证明与定理2基本类似,假设aÏ{Neigh(u)ÈzPeer(u)È{u}},仅在情形(3)有所区别:若xÎProv(u),x从u学到的长度为1的客户路由.虽然a是x的客户,由于a宣告的是AS长度为2的劫持路由,因此,x仍然优选u发起的正确路由.在这种情形下,u不会从x学到劫持路由,与题设矛盾.

综上所述,题设得证.

根据定理1、定理2,前缀劫持下的AS级自我免疫能力满足以下不等式:

(1)

(2)

根据定理3,下一跳劫持下的AS级自我免疫能力满足以下等式:

(3)

结合公式(1)~公式(3),无论是针对前缀劫持还是下一跳劫持,公式(2)都是Áu的上界.另外,推论2和假设4并不一定适用于所有的AS,进一步降低了AS对路由劫持的免疫能力.例如,若yuÇzPeer(u)¹Æ(假设4不成立),即使攻击者AS aÎzPeer(u),AS u也不一定能够实现自我免疫.不妨假设AS YÎyuÇzPeer(u),当$xÎPeer(u)使攻击者aÎzx时,Y恰好在从a到x的上坡路径上,由于Y有去往u的客户路由,它并不一定优选a发起的劫持路由,因此,x不一定能学到劫持路由,进而u的自我免疫失败.此外,实际情况中,攻击者AS试图劫持邻居AS的网络前缀时,它们不大可能将伪造的、用于实施攻击的路由宣告给邻居AS.因此,将公式(2)作为Áu的上界是合理的.接下来,我们基于公式(2)对当前Internet中的AS级免疫能力的上界进行评估.

鉴于实际采集的Internet拓扑的不完整性[18]以及商业关系推断算法的不准确性[19, 20],评估中采用了两个不同的拓扑图:拓扑1简称为CAIDA,基于CAIDA发布的2010年1月20日的互联网AS级拓扑和对AS间商业关系的推断[7];拓扑2简称为Gao,基于同一天从RouteViews以及RIPE-RIS项目采集到的路由表(主要是路由的AS_PATH属性),然后采用Gao算法[11]推断AS间的商业关系.两个拓扑的基本参数见表 3,两者在p2c,p2p连接所占比例上有明显的差异,体现了一定程度上的数据多样性.

对于推论2,CAIDA中有127个(0.38%),Gao中有199(0.58%)个AS的提供商闭包和客户闭包产生了重叠,即超过99%的自治系统满足推论2;对于假设4,CAIDA中有1 333个(3.98%),Gao中有1 533个(4.48%)个AS的提供商闭包和对等体的客户闭包产生了重叠,即超过95%的自治系统满足假设4.总体而言,违反推论2和假设4的自治系统所占比例很小,公式(2)作为Áu的上界能够反映绝大多数AS对于路由劫持的免疫能力.

评估同时考虑了Internet拓扑的层次特性和流量特性.在层次特性方面,我们将AS分为Tier1,Transit和Stub这3层,具体的方法是:

(1) 从一个预先选定的、公认的、小规模的Tier1集合出发(8个),每次将V\Tier1中与当前Tier1中所有AS均有连接、度数最大的AS加入到Tier1集合中,直到再也找不到这样的AS为止.算法终止时,一共得到了18个Tier1;

(2) 根据从RouteViews和RIPE-RIS收集的AS路径,只出现在路径最右边的AS被定义为是Stub(28 691个);

(3) 剩下的AS被划分为Transit(5 486个).

同时,为了更准确地刻画Internet的流量特性——一少部分稳定的前缀承载了Internet中绝大部分流量[21],内容服务提供商(Internet content provider,简称ICP)所在的自治系统受到了重点关注.具体方法如下:

首先,从Alexa[22]的站点排名中选取访问流量排名前300的网站的网址;然后,通过本地的DNS服务器以及GoogleDNS[23]和OpenDNS[24]将这些网址解析成IP地址;之后,使用RouteViews的BGP路由表将这些IP地址关联到宣告它们的AS;最后,借助于Whois数据库[25]和搜索引擎查询这些AS号所属ISP的名字,只有名字与网址存在一定关联的AS才被认为属于ICP.

使用这种方式,300个网址中有283个网址解析得到的IP地址成功地与AS号建立了关联,最终得到了182个被认定为ICP的AS,称为Traffic-Set.解析得到的AS号远少于网址数是因为一些跨国企业往往使用一个AS号来服务多个站点,例如,Google使用AS号15169提供服务的站点包括google.com,google.com.hk,google.de, google.co.uk等.

图 3展示了CAIDA和Gao拓扑下AS对路由劫持的免疫能力的补充累积分布(complementary cumulative distribution function,简称Ccdf).尽管表 3显示了CAIDA和Gao拓扑之间存在着显著的差异,但如图 3所示,两种拓扑中AS对路由劫持的免疫力的分布却非常接近.得益于更多的连接数、更高的p2p连接比例,Gao拓扑中AS的免疫力略高于CAIDA拓扑中的情形.但就整体而言,两个拓扑中,AS对路由劫持的免疫能力都很低. CAIDA中仅有16.8%的自治系统的免疫力大于0,这个比例在Gao中是17%.换言之,超过80%以上的自治系统对路由劫持完全没有免疫力;免疫力超过85%的AS的比例在CAIDA中是0.23%,在Gao中是0.26%.

图 4展示了Gao拓扑中不同类型的AS对路由劫持的免疫能力,可以得到以下结论:

(1) Tier1表现出了最强的免疫力,所有Tier1 AS的免疫力都高于95%,其原因在于,Tier1 AS及其对等体AS(也是Tier1 AS)有庞大的客户闭包;

(2) Transit,Stub和Traffic-Set中的AS均表现出了很低的免疫能力,且Stub的免疫力最差.其中,43.4%的Traffic-Set以及几乎全部的Stub对路由劫持没有免疫能力.免疫力超过85%的自治系统在Transit和Traffic-Set中所占的比重分别为1.28%和6.59%;

(3) 虽然Traffic-Set中的AS在整体上表现出了略强于Transit中AS的免疫能力,但仍然达不到保证其承载的Internet内容服务的安全性的要求.

为了直观地展示AS对路由劫持免疫力低下的原因,图 5标记了AS 0的免疫范围的上界.该范围具体包括: AS 0的直接邻居AS 5,AS 8,AS 13;AS 0的提供商(AS 5,AS 8)的直接客户AS 6,AS 7,AS 9;AS 0及其对等体AS 13的客户闭包中的AS.同时,图 5也展示了AS 14劫持AS 0的网络前缀时网络中AS的状态.

对于AS 0的服务提供商,BGP“只传播最优路由”和GR2是造成AS0难于从它们学到劫持路由的主要原因.以AS 0的间接服务提供商AS 1为例,AS 1从它的两个Tier1对等体(AS 2和AS 3)接收到了AS 14发起的劫持路由,但由于AS 0发起的客户路由具有更高的优先级(GR2)和BGP只传播最优路由的特性,它并不会优选劫持路由,自然也不会向其客户AS 4和AS 8传播此劫持路由.基于同样的原因,仅当攻击者AS是AS 5或AS 8的直接客户时,AS 5或AS 8才有可能优选劫持路由并向AS 0通告此劫持路由.

除了上述的BGP“只传播最优路由”和GR2,GR3是阻止AS 0的对等体和客户向其输出劫持路由的又一重要原因.根据GR3,对等体/客户只能向对等体/提供商输出客户路由,这使得仅当攻击者AS来自于AS 0本身的客户闭包或者AS 0的对等体的客户闭包时,AS 0才有可能通过对等体或客户学到劫持路由.以AS 0的一个对等体AS 13为例,即便AS 13优选从AS 12学到的劫持路由,受限于路由输出策略,它也不会向AS 0输出此劫持路由.

一个典型的AS(非Tier1自治系统)依赖其提供商AS来实现到网络中其他自治系统的可达性.当针对于它的路由劫持发生时,其提供商出于自身利益优选客户路由,导致攻击路由不能传播到受害者AS.这种提供商阻碍了自治系统自我感知路由劫持的现象称为提供商栅栏(provider barrier)现象.

提供商栅栏的存在,使自治系统仅能感知自身的客户闭包、对等体的客户闭包中的自治系统发起的路由劫持,以及以一定概率感知提供商的直接客户发起的路由劫持(定理1~定理3).对应于以上分析,为了提高AS对路由劫持的自我免疫能力,可以采取以下措施:

第1种方法是改变BGP中只传播最优路由的行为,将BGP改造成类似OSPF的路由协议,但这样违背了BGP的设计初衷,会显著降低BGP的可扩展性;

第2种方法是改变AS的路由选择和输出策略,但这与AS的利益诉求相矛盾,不会得到运营商的支持;

第3种方法是通过提升自己在Internet路由结构中的层次来扩展自身和对等体的客户闭包的范围,但此方法经济代价高昂,在实践中并不可行.

第4种方法是采用协同监测,越过提供商栅栏,从提供商之外的AS学习路由用于对路由劫持的检测.实验评估显示,Internet中绝大多数AS对路由劫持的免疫力都很低,具备了广泛的协同基础,但该方法能否成功还取决于对以下几个问题的解决:

(1) 兼容性.BGP是Internet的核心基础设施,如何保证协同监测交换的路由不扰乱现有的路由功能;

(2) 隐私保护.ISP视路由策略为商业秘密,协同需要ISP向协同伙伴透漏一部分路由信息,如何保证ISP对信息交换的控制并在不损害安全能力的前提下尽可能少地泄漏ISP的隐私;

(3) 有效性和准确性.由于缺乏准确的前缀-源AS对应关系和AS邻接关系,检测前缀劫持和下一跳劫持一直是公认的难题,如何降低路由劫持检测过程中的“漏检率”和“误检率”?此外,方法中应使用较成熟的技术,避免引入新的技术风险.

为了克服提供商栅栏,在AS级提高对路由劫持的免疫能力,我们提出了防范路由劫持的协同监测方法:参与协同的每个AS与它的协同邻居AS交换各自感兴趣的路由更新,并基于接收到的路由更新信息检测路由劫持.该方法的要点包括:

① 每个成员AS在域内设立一个监测器,定义相关于本AS的前缀集(一般是属于本AS的网络);

② 监测器在AS内部使用“只收不发”的BGP会话学习路由用于和协同邻居交换;

③ 在监测器之间,每个监测器从协同邻居只能学习到相关于本AS网络的路由,向每个协同邻居只输出相

关于该邻居的路由;

④ 监测器基于从邻居接收到的、相关于本AS所属网络的路由更新检测路由劫持.

由于每个参与者AS从协同邻居AS学到的路由并不能用于数据转发,因此本方法不会产生兼容性问题.具体地,监测器与域内路由器之间的BGP会话具有“只收不发”的特性,从监测邻居学到的路由不会在域内传播;监测器从协同邻居学到的路由相关于本AS所属网络,不存在将其用于转发数据的动机.此外,根据BGP规范,一个IP地址可用作转发数据的下一跳仅当该IP在IGP中可达,因此,将远端监测邻居的IP地址设为转发数据的下一跳并不可行.

本方法能够较好地保护参与者的隐私.在RouteViews和RIPE-RIS项目中,每个参与者被建议输出整个路由表,使得对参与者路由策略的推导相对容易.在本方法中,一方面参与者具有相当的灵活性,可以自主地决定向协同邻居暴露相关于哪些网络前缀的路由信息;另一方面,暴露的路由信息以多个片段的形式分布在不同的监测邻居之间,使得外界难于推断参与者的路由策略.

本方法使用源认证的思想由网络的拥有者本身对路由劫持进行检测,保证了检测的有效性和准确性,绕开了第三方难以区分正常路由变化和路由劫持的难题.同时我们认为,这种利己特性将有助于本方法的推广和应用.此外,本方法采用成对协同方式,每个参与者获得的安全能力并不取决于本方法的部署范围,而是取决于与之协同的AS的数量和分布.

下面,我们从协同监测体系结构、对路由劫持的检测和协同邻居选择这3个方面介绍本方法的设计和实现.

本方法在组织形式上以AS为基本单位,每个成员AS在域内设立一个协同监测器(cooperative monitor,下文中简称监测器).概念上,监测器由两个功能部件组成:路由组件和检测路由劫持的引擎组件.监测器使用路由组件运行BGP协议与其他成员交换路由变化,检测引擎基于路由组件接收到的BGP路由更新检测路由劫持.

监测器从所在的AS学习实时的路由视图,以便能够向与之协同的其他监测器提供路由更新,但并不将从其他监测器学来的路由输出到所在AS.前者通过路由组件与AS内的路由器(内部邻居)建立iBGP会话实现,后者通过配置监测器的路由输出策略实现.这种只收不发的BGP会话可以保证监测器输入的路由不会传播到监测器所在自治系统的内部,不影响原有的路由和数据转发功能.实际上,这种配置方式在现有的路由采集项目如RouteViews和RIPE-RIS中已经得到了广泛应用.也就是说,参与了RouteViews和RIPE-RIS项目的AS无需对域内的设施做任何改动,就可直接重用于协同监测方法的部署.

出于备份的目的,我们建议每个监测器与两个或两个以上的内部邻居互联.随着AS内iBGP拓扑组织形式的不同,监测器所连接的内部邻居也略有不同:

(1) 对于采用全互联拓扑的AS,监测器需要与其中任意两个或两个以上的路由器建立iBGP会话.例如,图 6中AS v的4个路由器R1,R2,R3和R4通过iBGP实现了全互联,AS v的监测器与R1和R4建立了iBGP会话;

(2) 对于采用路由反射来组织iBGP拓扑的AS,监测器需要与其中任意的两个或以上的路由反射器(RouteReflector,简称RR)建立iBGP会话,并将监测器配置为路由反射器的客户(RouteClient,简称RC).例如,图 6中AS u有两个RR(RR1和RR2)和3个RC(R1,R2,R3),AS u中的监测器与两个路由反射器RR1和RR2建立iBGP会话;

(3) 对于采用BGP联邦部署方式的AS,监测器只需加入其中任意一个联邦,并与该联邦内任意两台或以上的路由器建立iBGP会话即可.

属于不同AS的监测器之间,通过协同监测会话互联.协同监测会话本质上就是多跳步的eBGP会话.与BGP会话一样,协同监测会话使用TCP以实现可靠的通信,会话双方均采用MD5算法[26]防止消息被篡改.

监测器之间选择性地输出对方感兴趣、且符合本地策略的路由.考虑处在不同自治系统中的两个监测器u和v,每个监测器都需要定义相关于本AS的前缀集,记为Iu和Iv.一般而言,Iu中的前缀要么属于u,要么属于u的客户.协同检测会话(u,v)能够建立当且仅当双方均同意向对方发送对方感兴趣的路由更新,即u同意向v发送关于Iv中前缀的路由更新且v同意向u发送关于Iu中前缀的更新.当一方(u)提出建立协同监测会话的请求时,另一方(v)需要验证u是否合法地拥有Iu中的网络前缀.例如,通过查看RouteViews和RIPE-RIS项目发布的历史路由数据,检查Iu中前缀是否属于u;在反方向上,u也需要对Iv做同样的验证.

监测器u仅向v输出到相关于Iv中前缀(包括父前缀和子前缀)的路由,该策略可以通过prefix-list实现.例如,“ip prefix-list name permit A.B.C.D le 8 ge 32”表示A.B.C.D/8~A.B.C.D/32范围内的所有前缀.

按照AS u的管理员预定义的策略Pu,检测引擎对从监测邻居学到的路由变化进行检测以发现路由劫持.Pu定义为一个三元组Pu=áIu,Ou,Luñ.对于任意前缀dÎIu,Ou,d是u认为有资格宣告前缀d的自治系统集合,Lu,d是u认为有资格充当到前缀d的路由的下一跳AS的集合.给定任意前缀x,在Pu中查找最相关于x的前缀的过程记为Lookupu(x),该过程类似于“最长前缀匹配”,步骤如下:

(1) 若$dÎIu使x=d,存在精确匹配,返回d;

(2) 若$dÎIu且xÌd,即Iu中存在x的父前缀,返回具有最大前缀长度的x的父前缀;

(3) 若$dÎIu且dÌx,即Iu中存在x的子前缀,返回具有最小前缀长度的x的子前缀;

(4) 返回Æ.当Lookupu(x)返回Æ时,说明x与AS u不相关.

监测器u从监测邻居Mi接收到的路由更新反映了从Mi去往u所属网络的路由及变化.为了防范路由劫持,我们主要关注两类变化:

(1) 源AS的变化是否合理;

(2) 下一跳AS的变化是否合理.

在实现上,当接收到相关于前缀x的路由更新r时,只需将该路由的源AS和下一跳AS与Ou,d和Lu,d对比即可(其中,d=Lookupu(x)).

受限于计算资源、网络带宽等约束,参与者AS只能选取有限数量的协同邻居(假设最多只能有K个邻居).因此,每个参与者AS必须按照一定的邻居选取策略来选取协同邻居以获得最大的收益.我们主要考虑以下两种收益:安全能力和容错能力.

给定监测器v以及和它建立了协同监测会话的n个监测邻居Nv={M1,M2,…,Mn}(n≤K).为了测量一个AS参与协同监测所获得的安全能力,定义该AS的安全范围Sv.Sv是一个自治系统的集合,从Sv中的自治系统发起的针对于v的路由劫持事件都会被v通过协同监测网络所感知.该定义类似于之前自治系统免疫能力的定义,不同点在于:此时,v的协同邻居会扩展v的感知范围.为了刻画受害者AS(v)、攻击者AS(a)和协同邻居AS(u)三者之间的关系,我们首先定义指标函数qv,a,u.由连通性假设(假设3)可知,在路由劫持发生前,uÎV(v).当路由劫持发生后,若u优选了攻击者a发起的攻击路由,即uÎV(a),此时指标函数值为1;若u仍优选原有的到v的路由,则指标函数值为0.

(4)

然后,定义u提供给自治系统v的安全范围:

(5)

最后,给出v通过协同监测获得的安全能力,即安全范围Sv:

(6)

协同监测网络本身的容错能力是工程实践中很重要的考量.例如,一个自治系统希望劫持本自治系统网络的路由劫持事件至少能被k+1个协同邻居观察到,这样,即使在k个监测邻居同时失效的极端情况下,也能成功地检测到该路由劫持事件,称为k容错.为了衡量每个参与者构建的以自身为中心的协同监测网络的容错能力,首先定义覆盖频率fi,"iÎSv,如公式(7)所示,Sv中的自治系统i被fi个监测邻居所贡献的安全范围所覆盖:

(7)

然后,定义AS v建立的协同监测网络的k容错指数bk,即v的安全范围中覆盖频率高于k的AS所占比例:

(8)

不同于传统P2P网络中邻居选择多由算法决定,本方法的参与者可以自主地选择协同邻居,施加更充分的策略控制,如选择可信度高的AS、非商业竞争对手AS等.我们首先考虑以下3种典型的邻居选取策略:

策略1(随机选择策略(random selection policy,简称RSP)). 每个AS随机地选择参与协同的邻居,直到选择了K个邻居时终止.

策略2(优选连接策略(preferential attachment policy,简称PAP)). 每个AS以概率p(p=0.7)选择当前度数最高的、尚未与自己建立协同关系的AS,迭代至选择的邻居数达到K时终止.

策略3(基于安全范围的贪心策略(secure scope based greedy policy,简称SGP)). 每个AS首先计算其他AS相对于自身的安全范围,然后依次从高到低选择对自身安全范围贡献最大的K个节点.该策略需要对"uÎV计算其相对于v的安全范围,对V中节点,依据其安全范围的大小进行排序,最后从中选择K个节点.

除此之外,基于之前对AS自我免疫能力的分析,我们提出以下启发式策略:

策略4(启发式策略(heuristic selection policy,简称HSP)).

(1) 依据提供商栅栏现象,HSP优选不在自己的提供商闭包中的AS;

(2) AS对路由劫持的自我免疫能力反映了AS接收到攻击路由的可能性,HSP优先选择路由层次中处于较高位置的AS,如Tier1;

(3) 根据定理1,AS能够对自身的客户闭包、对等体的客户闭包中的AS发起的路由劫持免疫,因此,HSP不选择这一类AS作为协同邻居;

(4) AS路径长度是路由选择的一个重要指标,HSP优先选择距离自己较远的AS作为协同邻居.当路由劫持发生时,它们优选本AS发起的路由的可能性更小,被攻击路由污染的概率更大.

本节以前缀劫持为例,着重考察协同监测的安全能力,并对不同邻居选取策略下的安全效果进行横向比较.

每个AS参与协同监测所获得的安全能力取决于其协同监测邻居向它贡献的安全范围.根据公式(4)、公式(5),计算安全范围的关键在于计算指标函数qv,a,u.具体地,给定受害者AS v,攻击者AS a和协同邻居u,计算该指标函数需要解决以下两个问题:

(1) AS路径预测,需要预测v宣告前缀d时,该前缀从v到u的传播路径(受害者路径),以及a宣告同一前缀d时,该前缀从a到u的传播路径(攻击者路径);

(2) 路由选择模拟,需要预测u在受害者路径和攻击者路径之间做出的路由选择.

问题(2)可以简化为依次优选客户路由、对等体路由、提供商路由(GR2)和具有更短AS路径长度的路由,但问题(1)中,AS间的路径预测却是一个难题.Mao等人在给定AS路径第1跳的情况下,仅获得了70%~88%的准确率[19];Qiu等人给出了预测准确率的上界是90%[20].

为了避免路径预测引入的偏差,本评估方法使用现实存在的AS路径来计算受害者路径、攻击者路径和指标函数,计算过程如表 4所示.给定AS v,aÎV和一个RouteViews或RIPE-RIS项目的数据采集点u,表 4的第2行~第5行从u的路由表Ribu中提取v和a宣告的前缀集合Dv,Da,以及Dv,Da中的前缀到u的传播路径集P(v®u)和P(a®u).由于一个AS一般拥有多个网络前缀,当a发起对v的前缀劫持时,我们假设a从v拥有的前缀中随机挑选一个(记为d)并劫持该前缀,因此,受害者路径为pÎP(v®u)的概率(wp)正比于v宣告的、以p为传播路径的前缀数量(第6行).类似地,攻击者路径为qÎP(a®u)的概率(wq)正比于a宣告的、以q为传播路径的前缀数量(第7行).综上,当a发起针对于v的前缀劫持时,受害者路径和攻击者路径分别是p和q的概率可以表示为wpwq,见第8行.第8行中,Selection(p,q)在路径p和q之间做路由选择,当优选路径q(攻击者路径)时返回1,否则返回0.最后,第9行将临时变量var与预设的置信阈值Th进行比较,仅当var高于此阈值时,才认为指标函数qv,a,u=1.在本文中,我们将此阈值设定为95%.

对于任意AS vÎV,通过限定NvÍM(Nv是v选择的协同邻居AS集合,M是RouteViews和RIPE-RIS项目的数据采集点AS集合),基于上述方法就可以计算每个AS uÎNv向v贡献的安全范围,并根据公式(6)计算出v通过协同监测获得的安全能力Sv.同时,根据公式(7)和公式(8)还可以计算v建立的协同监测网络的k容错指数.

评估实验使用2010年1月20日RouteViews和RIPE-RIS项目发布的路由表作为数据集.当时,这两个项目共有717个数据采集点,我们只选取公开了整个路由表的采集点.具体地,只有当其路由表包含超过300 000个前缀时,我们才认为该数据采集点公开了整个路由表,共得到224个这样的采集点.在去除数据采集点之间的冗余,例如同一个AS可能会同时向RouteViews和RIPE-RIS项目提供数据,我们最后一共得到了113个有效的数据采集点AS,包含14个Tier1,90个Transit和9个Stub.

在实验部分,我们首先验证协同监测机制取得的安全效果;然后,通过考察各种邻居选择策略下参与者AS获得的安全范围、1-容错指数、选择的邻居节点的度数.我们对4种邻居选择策略进行了比较.

理论上,协同监测能够改善参与者AS对前缀劫持的免疫能力.为了验证改善效果,我们从113个数据采集点AS中随机选取若干个AS作为一组(采用RSP策略),然后计算这些AS两两之间建立协同关系后对前缀劫持的免疫能力.对于每个特定的成员数量,我们将这个过程重复1 000遍,并在图 7中展示了这些AS参与协同监测之前和之后免疫能力的平均值/标准差.如图 7所示,参与协同监测之前,AS对前缀劫持的免疫能力接近于0.相比之下,协同监测组即使只包含5个AS,也能使免疫能力增强到60%以上.此外,协同监测提供的安全能力的平均值/标准差随着协同监测组中成员数量的增长而提高/减小,但这种提高/减小在组中成员数量超过40以后变得不明显.这种现象表明,部署者AS只需要与一小部分AS建立协同关系,就可以达到较好的免疫效果.

协同监测方法为参与者提供的安全范围的大小是最重要的安全指标.如图 8所示,在邻居数较少(K值较小)的情况下,SGP和HSP具有显著的优势.随着K值的增加,4种策略的差距逐渐缩小.当K达到25时,RSP,PAP, SGP,HSP产出的安全范围的平均大小分别是29 037(85.4%),31 018(91.2%),32 715(96.2%)和32 792(96.4%).这也意味着,一个监测器仅仅选择25个AS并与之建立协同关系,就可以使自身对路由劫持的免疫力达到95%以上.当K超过40之后,4种策略所提供的安全范围的差别已经很小,说明协同网络的构建在邻居数较多的情况下,其效果并不依赖于节点选择策略,在部署实践中具有较强的操作性.

对4种策略下的1-容错指数的评估如图 9所示.与图 8一样,SGP和HSP策略表现最好,随后是PAP策略, RSP策略表现最差.虽然HSP策略在安全范围方面的表现略好于SGP策略,但两者在1-容错指数方面的表现基本相同.在K=25时,4种策略下的1-容错指数分别是82.1%,89.4%,96.2%和96.2%.当K超过25之后,1-容错指数的增长开始放缓.如果采用SGP或HSP策略,在K=25时即可达到比较满意的容错水平.

直观上,协同主要在规模相近的运营商之间发生.本文使用各种策略下所选取的邻居节点的平均度数来衡量AS间进行协同的难易程度,如图 10所示.PAP策略偏好于度数最大的节点,因此选取的邻居节点也具有最大的平均度数,紧接着的是SGH和HSP策略,RSP策略产出的拓扑中邻居节点的平均度数最低.同时也注意到,随着K的增大,除RSP之外的其他3种策略所选择的邻居节点的平均度数迅速减少.这是因为除RSP之外的3种策略虽然着眼点不同,但为了通过选取有限数量的邻居达到最大效益,都倾向于选择连通性较好的自治系统作为监测邻居,产生了类似于PAP策略的效果.

虽然SGP和HSP策略的效果相似,但HSP策略的复杂度远低于SGP策略,因而具有更好的实用性.

路由监测是防范路由劫持的一类重要方法.不同于对BGP安全模型的研究[27],监测方法不依赖于全网范围内的PKI体系,无需修改BGP协议,且容易增量部署,近年来得到了学术界的广泛关注.路由监测具体分为对控制平面的监测[28]、对数据平面的监测[29]以及对数据平面和控制平面的联合监测[30]:

· 对控制平面进行监测开销较小,但面临着3个方面的问题:

一是监测效果受限于数据采集点的数量和覆盖范围[31].运营商出于保护商业隐私的考虑,很少有AS愿意无条件地公开自己的BGP数据.如本文实验部分中,绝大多数RouteViews和RIPE- RIS的采集点都仅公开了部分路由数据;

二是对控制平面的监测多采用集中式部署,需要用户主动注册网络前缀-源AS的对应关系[28],对路由劫持的检测效果取决于注册数据的时效性和准确性;

三是在路由劫持发生时,由于受害者网络已不可达,该类方法还面临着如何通知受害者的困局.

本文方法也属于控制平面的监测机制,参与协同的AS互为监测数据的来源,并直接受益于协同行为,解决了路由监测中数据难于获取的问题.每个参与者AS独立地检测针对所属网络的路由劫持,避免了第三方难以区分正常路由变化和路由劫持的问题;而且对路由劫持的检测在本地进行,也避免了路由劫持时的通信困局;

· 对数据平面的监测多从运营商本身的角度出发,如iSPY[29],不依赖于实时的BGP数据,易于部署,但所依赖的Ping,Traceroute,TCP Ping等手段也是网络攻击的基本手段,常被运营商视为威胁而被阻塞;其次,该类机制需要周期性、持续性地探测Internet,会消耗较多的网络带宽;最后,该类机制具有较高的误检率和漏检率,可用性有待改善;

· 对数据、控制平面联合监测的方法兼具两者的优点和缺点,开销较大,只适合于对少数重点网络进行监测.

参与协同监测的AS在互利互惠的基础上对BGP路由的可信性进行分析,能够克服BGP路由中单个AS的视图局部性问题.网络运营商是极端重视隐私的群体,如何在开展协同获得较高安全能力的同时保护运营商的隐私,是协同监测迫切需要解决的问题,也是协同监测能否走向应用的关键.在这个方面,Harlan等人设计了一种根据其他AS的投票结果评价路由信息可信性的机制[32],该机制只要求参与者AS回答“是”或“否”,就能够较好地保护参与者的隐私.但该方法只能给出统计意义上的结论,准确率值得商榷;且该方法不能直接用于检测路由劫持,需要引入另外的检测机制.Goodell等人提出的IRV方法具有和本文方法类似的结构,每个参与者AS需要在域内设立IRV服务器,回答其他AS发送来的路由验证请求,并根据本地路由策略、网络拓扑等对给定路由的真实性进行判断和回答[33].在这种协同方式下,参与者AS需要向外界暴露较多的策略信息.以上两种方法均未对查询请求的范围进行限制,因此很容易被用来实现一些恶意的目的.例如,通过大量、反复的查询,推断目标AS的直接邻居.本文方法中,每个AS只向协同邻居请求相关于所属网络的路由变化,并不要求其他参与者AS直接暴露自己的路由策略、网络拓扑等隐私信息,是一种更合理的协同策略.此外,每个参与者所暴露的路由信息以多个片段的形式分布在不同的协同邻居之间,外界难以推断参与者的路由策略.国内学术界也对通过在AS之间引入协同机制防范路由劫持进行了一些研究.例如,刘欣等人设计了专用于检测前缀劫持的协作监测机制[34],但该方法需要在参与者之间使用新的协议机制,且不能检测下一跳劫持.胡宁等人设计了协同监测下的信息共享机制,但并未涉及对路由异常的监测[35].

本文方法也存在一定的局限性.协同监测网络是建立在Internet之上的层叠网,因此也继承了这一类层叠网所面临的一系列问题[36],如层叠网本身的安全性问题,在以后的工作中需要进一步改进和完善.

致谢 在此,我们向对本文提出宝贵修改意见的评审老师和同行表示衷心的感谢!